home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / GCC 1.37.1r14 / usr / lib / stdlib / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-20  |  7.9 KB  |  277 lines  |  [TEXT/CPED]
  1. /*-
  2.  * Copyright (c) 1980, 1983, 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if defined(LIBC_SCCS) && !defined(lint)
  35. static char sccsid[] = "@(#)qsort.c    5.9 (Berkeley) 2/23/91";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #include <sys/types.h>
  39. #include <stdlib.h>
  40.  
  41. /*
  42.  * MTHRESH is the smallest partition for which we compare for a median
  43.  * value instead of using the middle value.
  44.  */
  45. #define    MTHRESH    6
  46.  
  47. /*
  48.  * THRESH is the minimum number of entries in a partition for continued
  49.  * partitioning.
  50.  */
  51. #define    THRESH    4
  52.  
  53. static void insertion_sort(register char *bot,int nmemb,register int size,int (*compar)());
  54. static void quick_sort(register char *bot,int nmemb,register int size,int (*compar)());
  55.  
  56. void
  57. qsort(bot, nmemb, size, compar)
  58.     void *bot;
  59.     size_t nmemb, size;
  60.     int (*compar) __P((const void *, const void *));
  61. {
  62.  
  63.     if (nmemb <= 1)
  64.         return;
  65.  
  66.     if (nmemb >= THRESH)
  67.         quick_sort(bot, nmemb, size, compar);
  68.     else
  69.         insertion_sort(bot, nmemb, size, compar);
  70. }
  71.  
  72. /*
  73.  * Swap two areas of size number of bytes.  Although qsort(3) permits random
  74.  * blocks of memory to be sorted, sorting pointers is almost certainly the
  75.  * common case (and, were it not, could easily be made so).  Regardless, it
  76.  * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
  77.  * arithmetic gets lost in the time required for comparison function calls.
  78.  */
  79. #define    SWAP(a, b) { \
  80.     cnt = size; \
  81.     do { \
  82.         ch = *a; \
  83.         *a++ = *b; \
  84.         *b++ = ch; \
  85.     } while (--cnt); \
  86. }
  87.  
  88. /*
  89.  * Knuth, Vol. 3, page 116, Algorithm Q, step b, argues that a single pass
  90.  * of straight insertion sort after partitioning is complete is better than
  91.  * sorting each small partition as it is created.  This isn't correct in this
  92.  * implementation because comparisons require at least one (and often two)
  93.  * function calls and are likely to be the dominating expense of the sort.
  94.  * Doing a final insertion sort does more comparisons than are necessary
  95.  * because it compares the "edges" and medians of the partitions which are
  96.  * known to be already sorted.
  97.  *
  98.  * This is also the reasoning behind selecting a small THRESH value (see
  99.  * Knuth, page 122, equation 26), since the quicksort algorithm does less
  100.  * comparisons than the insertion sort.
  101.  */
  102. #define    SORT(bot, n) { \
  103.     if (n > 1) \
  104.         if (n == 2) { \
  105.             t1 = bot + size; \
  106.             if (compar(t1, bot) < 0) \
  107.                 SWAP(t1, bot); \
  108.         } else \
  109.             insertion_sort(bot, n, size, compar); \
  110. }
  111.  
  112. static void
  113. quick_sort(bot, nmemb, size, compar)
  114.     register char *bot;
  115.     register int size;
  116.     int nmemb, (*compar)();
  117. {
  118.     register int cnt;
  119.     register u_char ch;
  120.     register char *top, *mid, *t1, *t2;
  121.     register int n1, n2;
  122.     char *bsv;
  123.  
  124.     /* bot and nmemb must already be set. */
  125. partition:
  126.  
  127.     /* find mid and top elements */
  128.     mid = bot + size * (nmemb >> 1);
  129.     top = bot + (nmemb - 1) * size;
  130.  
  131.     /*
  132.      * Find the median of the first, last and middle element (see Knuth,
  133.      * Vol. 3, page 123, Eq. 28).  This test order gets the equalities
  134.      * right.
  135.      */
  136.     if (nmemb >= MTHRESH) {
  137.         n1 = compar(bot, mid);
  138.         n2 = compar(mid, top);
  139.         if (n1 < 0 && n2 > 0)
  140.             t1 = compar(bot, top) < 0 ? top : bot;
  141.         else if (n1 > 0 && n2 < 0)
  142.             t1 = compar(bot, top) > 0 ? top : bot;
  143.         else
  144.             t1 = mid;
  145.  
  146.         /* if mid element not selected, swap selection there */
  147.         if (t1 != mid) {
  148.             SWAP(t1, mid);
  149.             mid -= size;
  150.         }
  151.     }
  152.  
  153.     /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */
  154. #define    didswap    n1
  155. #define    newbot    t1
  156. #define    replace    t2
  157.     didswap = 0;
  158.     for (bsv = bot;;) {
  159.         for (; bot < mid && compar(bot, mid) <= 0; bot += size);
  160.         while (top > mid) {
  161.             if (compar(mid, top) <= 0) {
  162.                 top -= size;
  163.                 continue;
  164.             }
  165.             newbot = bot + size;    /* value of bot after swap */
  166.             if (bot == mid)        /* top <-> mid, mid == top */
  167.                 replace = mid = top;
  168.             else {            /* bot <-> top */
  169.                 replace = top;
  170.                 top -= size;
  171.             }
  172.             goto swap;
  173.         }
  174.         if (bot == mid)
  175.             break;
  176.  
  177.         /* bot <-> mid, mid == bot */
  178.         replace = mid;
  179.         newbot = mid = bot;        /* value of bot after swap */
  180.         top -= size;
  181.  
  182. swap:        SWAP(bot, replace);
  183.         bot = newbot;
  184.         didswap = 1;
  185.     }
  186.  
  187.     /*
  188.      * Quicksort behaves badly in the presence of data which is already
  189.      * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2.
  190.      * To avoid this worst case behavior, if a re-partitioning occurs
  191.      * without swapping any elements, it is not further partitioned and
  192.      * is insert sorted.  This wins big with almost sorted data sets and
  193.      * only loses if the data set is very strangely partitioned.  A fix
  194.      * for those data sets would be to return prematurely if the insertion
  195.      * sort routine is forced to make an excessive number of swaps, and
  196.      * continue the partitioning.
  197.      */
  198.     if (!didswap) {
  199.         insertion_sort(bsv, nmemb, size, compar);
  200.         return;
  201.     }
  202.  
  203.     /*
  204.      * Re-partition or sort as necessary.  Note that the mid element
  205.      * itself is correctly positioned and can be ignored.
  206.      */
  207. #define    nlower    n1
  208. #define    nupper    n2
  209.     bot = bsv;
  210.     nlower = (mid - bot) / size;    /* size of lower partition */
  211.     mid += size;
  212.     nupper = nmemb - nlower - 1;    /* size of upper partition */
  213.  
  214.     /*
  215.      * If must call recursively, do it on the smaller partition; this
  216.      * bounds the stack to lg N entries.
  217.      */
  218.     if (nlower > nupper) {
  219.         if (nupper >= THRESH)
  220.             quick_sort(mid, nupper, size, compar);
  221.         else {
  222.             SORT(mid, nupper);
  223.             if (nlower < THRESH) {
  224.                 SORT(bot, nlower);
  225.                 return;
  226.             }
  227.         }
  228.         nmemb = nlower;
  229.     } else {
  230.         if (nlower >= THRESH)
  231.             quick_sort(bot, nlower, size, compar);
  232.         else {
  233.             SORT(bot, nlower);
  234.             if (nupper < THRESH) {
  235.                 SORT(mid, nupper);
  236.                 return;
  237.             }
  238.         }
  239.         bot = mid;
  240.         nmemb = nupper;
  241.     }
  242.     goto partition;
  243.     /* NOTREACHED */
  244. }
  245.  
  246. static void
  247. insertion_sort(bot, nmemb, size, compar)
  248.     char *bot;
  249.     register int size;
  250.     int nmemb, (*compar)();
  251. {
  252.     register int cnt;
  253.     register u_char ch;
  254.     register char *s1, *s2, *t1, *t2, *top;
  255.  
  256.     /*
  257.      * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm
  258.      * S).  Insertion sort has the same worst case as most simple sorts
  259.      * (O N^2).  It gets used here because it is (O N) in the case of
  260.      * sorted data.
  261.      */
  262.     top = bot + nmemb * size;
  263.     for (t1 = bot + size; t1 < top;) {
  264.         for (t2 = t1; (t2 -= size) >= bot && compar(t1, t2) < 0;);
  265.         if (t1 != (t2 += size)) {
  266.             /* Bubble bytes up through each element. */
  267.             for (cnt = size; cnt--; ++t1) {
  268.                 ch = *t1;
  269.                 for (s1 = s2 = t1; (s2 -= size) >= t2; s1 = s2)
  270.                     *s1 = *s2;
  271.                 *s1 = ch;
  272.             }
  273.         } else
  274.             t1 += size;
  275.     }
  276. }
  277.